package lee.study.Data_Struct.TestSort;

import java.util.Arrays;

public class mergeSort1 {//非递归实现归并排序

    public static void mergeNor(int[] array, int gap) {
        int[] ret = new int[array.length];
        int k = 0;//ret的下标
        int s1 = 0;
        int e1 = s1 + gap - 1;
        int s2 = e1 + 1;
        int e2 = s2 + gap - 1 < array.length ? s2 + gap - 1 : array.length - 1;
        //e2位置：如果s2+gap-1大于数组长度说明越界了，这时取array.length-1。
        //如果没有，则还是取s2+gap-1。

        while (s2 < array.length) {//如果s2大于数组长度，则第二段数据只有一个归并段
            //1.满足循环条件则表示肯定有两个归并段

            //2.对应的s1位置和s2位置进行比较
            while (s1 <= e1 && s2 <= e2) {
                if (array[s1] > array[s2]) {
                    ret[k++] = array[s2++];
                } else {
                    ret[k++] = array[s1++];
                }
            }
            //3.在2步骤的比较过程中，肯定会有一个归并段先走完
            //4.判断哪个归并段没走完，把剩下的数据拷贝到目标数组中
            while (s1 <= e1) {
                ret[k++] = array[s1++];
            }
            while (s2 <= e2) {
                ret[k++] = array[s2++];
            }
            //5.接着确定新的s1，e1，s2，e2。
            s1 = e2 + 1;
            e1 = s1 + gap - 1;
            s2 = e1 + 1;
            e2 = e2 + gap - 1 > array.length ? array.length : e2 + gap - 1;


        }
        //6.还需要判断是否有另外的归并段。
        //只有s1一个归并段时，直接将s1~~~array.length-1段的数据拷贝到ret中
        while (s1 < array.length - 1) {
            ret[k++] = array[s1++];
        }

        for (int i = 0; i < array.length-1; i++) {
            array[i] = ret[i];
        }
    }

    public static void mergeSort1(int[] array) {
        for (int gap = 1; gap < array.length; gap = gap * 2) {
            mergeNor(array, gap);
        }
    }

    public static void main(String[] args) {
        int[] array = {1, 6, 3, 8, 2, 9, 11, 75, 23};
        mergeSort1(array);
        System.out.println(Arrays.toString(array));
    }

}
